'''
@author: Kevin Zhao
@data:Jan 3,2013 
@note:

Quick-Sort
Chapter 7.1

Exercise 7.1-2,7.1-4
'''
def exchange(A_index, B_index, array):
    temp = array[A_index]
    array[A_index] = array[B_index]
    array[B_index] = temp

def partition(A, p, r):
    i = p - 1
    for j in range(p, r):
        if A[j] <= A[r]:
            i += 1
            exchange(i, j, A)
    exchange(r, i + 1, A)
    return i + 1
'''
Exercise 7.1-4
'''
def partition_V3(A, p, r):
    i = p - 1
    for j in range(p, r):
        if A[j] >= A[r]:
            i += 1
            exchange(i, j, A)
    exchange(r, i + 1, A)
    return i + 1
'''
Exercise 7.1-2
'''
def partition_V2(A, p, r):
    i = p - 1
    small_group_size = large_group_size = 0
    for j in range(p, r):
        if A[j] < A[r] or A[j] == A[r] and small_group_size < large_group_size:
            i += 1
            exchange(i, j, A)
            small_group_size +=1
        else:
            large_group_size+=1
    exchange(r, i + 1, A)
    return i + 1
def quick_sort(A, p, r):
    if p < r:
#        pivot = partition(A,p,r)
#        pivot = partition_V2(A, p, r)
        pivot = partition_V3(A, p, r)
        quick_sort(A, p, pivot - 1)
        quick_sort(A, pivot + 1, r)
    
    
A = [13,19,9,5,12,8,7,4,21,2,6,11]
#A = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
p = 0
r = len(A) - 1
quick_sort(A, p, r)
print A
